package C041;

/**
 * ClassName: C02
 * Package: C041
 * Description:
 *
 * @Author BCXJ
 * @Create 2025/2/2 20:31
 * @Version 1.0
 * @Since 1.0
 */
public class C02 {
    public static void main(String[] args) {
        System.out.println(nthMagicalNumber(1000000000, 40000, 40000));
    }

    public static int nthMagicalNumber(int n, int a, int b) {
        long l = 0, r = (long) Math.min(a, b) * n, m = 0;
        long lcm = lcm(Math.max(a, b), Math.min(a, b));
        long midres = 0;
        while(l <= r) {
            m = l + ((r - l) >> 1);
            if(m / a + m / b - m / lcm >= n) {
                r = m - 1;
                midres = m;
            } else {
                l = m + 1;
            }
        }

        return (int) (midres % 1000000007);
    }

    // a > b
    public static int lcm(int a, int b) {
        return a / gcd(a, b) * b;
    }

    public static int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }

}
